package com.demo.java.OD151_200.OD156;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【计算堆栈中的剩余数字】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145758241
 */
public class OdMain {
    // 使用栈存储正在处理的元素
    public static Stack<Integer> mStack = new Stack<>();

    public static void main(String[] args) {
        // 输入处理
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();

        String[] numsStrList = line.split(" ");
        int[] nums = new int[numsStrList.length];
        for (int i = 0; i < numsStrList.length; i++) {
            nums[i] = Integer.parseInt(numsStrList[i]);
        }

        // 处理每个数字
        for (int i = 0; i < nums.length; i++) {
            pushAttempt(nums[i]);
        }

        // 输出栈中的剩余元素
        StringBuilder result = new StringBuilder();
        while (!mStack.empty()) {
            result.append(mStack.pop()).append(" ");
        }
        System.out.println(result.toString().trim());
    }

    // 尝试将当前数字压入栈，若有合适的组合则进行弹出
    public static void pushAttempt(int num) {
        int temp = 0;
        // 从栈顶往下遍历，寻找是否能找到合适的组合
        for (int i = mStack.size() - 1; i >= 0; i--) {
            temp += mStack.get(i);
            // 如果找到了匹配的组合，弹出栈内元素并递归处理
            if (temp == num) {
                int stackSize = mStack.size();
                // 弹出匹配的元素
                for (int j = i; j < stackSize; j++) {
                    mStack.pop();
                }
                // 递归调用，将两倍的和压入栈中
                pushAttempt(temp * 2);
                return;
            } else if (temp > num) {
                // 若当前和大于目标值，停止遍历
                break;
            }
        }
        // 如果没有找到匹配，直接将当前数字压入栈
        mStack.push(num);
    }
}